      
      #include <iostream>
      #include <vector>
      using namespace std;

      int quickPartition(vector<int>& nums, int start, int end, int target) {
        // 随机取一个数作为基准
        srand(time(nullptr));
        int random = rand() % (end - start + 1) + start;
        int base = nums[random];
        // 将该数放到待快排区间开头第一个元素
        swap(nums[start], nums[random]);
        int index = start;
        // 从待快排区间的第二个元素开始，依次与base比较，如果大于等于base则将该元素
        // 交换到index + 1位置，index++，使得最终index前面的元素都比base大。
        for (int i = start + 1; i <= end; ++i) {
            if (nums[i] >= base) {
                swap(nums[index+1], nums[i]);
                index++;
            }
        }
        // base存放在区间开头，现在需要把它交换到index位置，这就是它在整个有序数组中的位置。
        swap(nums[index], nums[start]);
	
        // 如果index小于target，需要在右边区间继续快排查找，否则到在边区间查找，
        // 如果等于已经找到目标值不需要递归，这里这么做优化了传统快排的复杂度。
        if(index == target) {
            return nums[index];
        }
        else if (index < target) {
            return quickPartition(nums, index + 1, end, target);
        }
        else if (index > target) {
            return quickPartition(nums, start, index - 1, target);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        // 方法1. 快速排序的分区思想，快排的思想是一次找出一个数的正确位置，
        // 并使得该数左边的元素都比它小，该数右边的元素都比它大，要找出第k
	// 大的元素，只需要在快排的时候采用降序排序，找到下标为k-1的元素即可。

       return quickPartition(nums, 0, nums.size() - 1, k - 1);   

  //暴力破解 
 #if 0      
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
 #endif       
 }

 int main()
 {
    std::vector<int> nums = {3,2,1,5,6,4}; //654321

    std::cout << findKthLargest(nums, 3) << std::endl;
 }